package offer;

import java.util.ArrayList;
import java.util.List;

@FunctionalInterface
public interface LuckyNumbers {
    List<Integer> luckyNumbers (int[][] matrix);
}
class LuckyNumbersImpl1 implements LuckyNumbers{

    /**
     * o(mn*(m + n))
     * @param matrix
     * @return
     */
    @Override
    public List<Integer> luckyNumbers(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            int min = matrix[i][0];
            int minCol = 0;
            for (int j = 1; j < n; j++) {
                if(matrix[i][j] < min){
                    min = matrix[i][j];
                    minCol = j;
                }
            }
            boolean isLuckyNumber = true;
            for (int k = 0; k < m; k++) {
                if(min < matrix[k][minCol]){
                    isLuckyNumber = false;
                    break;
                }
            }
            if(isLuckyNumber){
                ans.add(min);
            }
        }
        return ans;
    }
}
class LuckyNumbersImpl2 implements LuckyNumbers{

    /**
     * 时间o(mn),空间o(m+n)
     * 使用o(m+n)的空间来记录行中的最小列和列中的最大行，然后按行检查
     * @param matrix
     * @return
     */
    @Override
    public List<Integer> luckyNumbers(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[] rowMins = new int[m];
        int[] colMaxs = new int[n];
        List<Integer> ans = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            int min = matrix[i][0];
            int minCol = 0;
            for (int j = 0; j < n; j++) {
                if(matrix[i][j] < min){
                    min = matrix[i][j];
                    minCol = j;
                }
            }
            rowMins[i] = minCol;
        }
        for (int j = 0; j < n; j++) {
            int max = matrix[0][j];
            int maxRow = 0;
            for (int i = 0; i < m; i++) {
                if(matrix[i][j] > max){
                    max = matrix[i][j];
                    maxRow = i;
                }
            }
            colMaxs[j] = maxRow;
        }
        for (int i = 0; i < m; i++) {
            int minCol = rowMins[i];
            int maxRow = colMaxs[minCol];
            if(maxRow == i){
                ans.add(matrix[maxRow][minCol]);
            }
        }
        return ans;
    }

}